ABC256 D - Union of Interval

提出

WA
n = int(input())
lr = [list(map(int, input().split())) for _ in range(n)]
# minとmaxの保持
lr.sort()
tmpl = lr[0][0]
tmpr = lr[0][1]
for i in range(1, n):
if (lr[i][0] <= tmpr):
continue
else:
print(tmpl, lr[i][1])
tmpl = lr[i][0]
tmpr = lr[i][1]


解答

n = int(input())
lr = [list(map(int, input().split())) for _ in range(n)]
lr.sort()
# 今の区間左側
nowL = lr[0][0]
# 今の区間右側
nowR = lr[0][1]
for i in range(1,n):
# 次の(i番目の)区間左側
nextL = lr[i][0]
# 次の(i番目の)区間右側
nextR = lr[i][1]
# 「今の右側」<「次の左側」
if nowR < nextL:
# [nowL,nowR)は絶対に必要な区間
print(nowL, nowR)
# 今の区間を更新
nowL = nextL
nowR = nextR
# それ以外(「次の左側」≤「今の右側」)
else:
# 「今の右側」<「次の右側」
if nowR < nextR:
# 区間を更新(右側を広げる)
nowR = nextR
# 最後に区間を出力
print(nowL, nowR)

メモ


提出

import bisect
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
print(xy)
# 10 20
# 20 30
# 40 50
# 10-20
# 20-30 40-50
# 10 40
# 30 60
# 20 50
# 10-------40
# 30-------60
# 20-------50
# 非連続で区切る
# 最大、最小 l, r を追加していっても探索しないといけない
# 単純増加
l, r = [], []
for x, y in xy:
i = bisect.bisect_left(l, x)
j = bisect.bisect_left(r, y)

Related